package class17_Graph;

import class15to16_UnionSet.UnionFind;
import class17_Graph.graph.Edge;
import class17_Graph.graph.Graph;
import class17_Graph.graph.Node;

import java.util.*;

public class GraphUtils {
    public static List<Node> BFS(Graph graph) {
        LinkedList<Node> queue = new LinkedList<>();
        LinkedList<Node> visited = new LinkedList<>();
        Node start = graph.nodes.get(0);//获取第一个结点
        queue.add(start);
        visited.add(start);

        while(!queue.isEmpty()){
            Node cur = queue.poll();
            for(Node n: cur.nexts){
                if(!visited.contains(n)){
                    queue.add(n);
                    visited.add(n);
                }
            }
        }
        return visited;
    }
    public static List<Node> DFS(Graph graph){
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Node> visited = new LinkedList<>();

        Node start = graph.nodes.get(0);
        stack.push(start);
        visited.add(start);

        while(!stack.isEmpty()){
            Node cur = stack.peek();

            if(cur.nexts.size()==0){
                stack.pop();
                continue;
            }

            for(Node next: cur.nexts){
                if(!visited.contains(next)){
                    stack.push(next);
                    visited.add(next);
                    break;
                }
                else{//访问过，而且已经是最后一个节点
                    if(next==cur.nexts.get(cur.nexts.size()-1))
                        stack.pop();
                }
            }
        }

        return visited;
    }

    public static List<Node> TopologySort(Graph graph){
        LinkedList<Node> queue = new LinkedList<>();
        LinkedList<Node> visited = new LinkedList<>();

        while(!graph.nodes.isEmpty() || !queue.isEmpty()){
            Set<Integer> keySet = graph.nodes.keySet();
            LinkedList<Integer> shouldDeleted = new LinkedList<>();
            for(int key: keySet){
                Node n = graph.nodes.get(key);
                if(n.in==0){
                    shouldDeleted.add(n.value);
                }
            }
            for(int index:shouldDeleted){
                queue.add(graph.nodes.get(index));
                for(Node next: graph.nodes.get(index).nexts){
                    next.in--;
                }
                graph.nodes.remove(graph.nodes.get(index).value);
            }
            Node cur = queue.poll();
            visited.add(cur);
        }

        return visited;
    }

    public static List<Edge> kruskal(Graph graph){
        LinkedList<Edge> edges = new LinkedList<>();

        Node[] nodes = new Node[graph.nodes.size()];
        for(int i=0;i<nodes.length;i++){
            nodes[i] = graph.nodes.get(i);
        }
        UnionFind<Node> uf = new UnionFind<>(nodes);
        PriorityQueue<Edge> heap= new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge e1, Edge e2){
             return e1.weight-e2.weight;
            }
        });

        for(Edge e: graph.edges){
            heap.add(e);
        }

        while(uf.numOfSets()>1){
            Edge e = heap.poll();
            Node a = e.from;
            Node b = e.to;
            if(!uf.isSameSet(a,b)){
                edges.add(e);
                uf.union(a,b);
            }
        }
        return edges;
    }

    public static List<Edge> prim(Graph graph){
        LinkedList<Edge> edges = new LinkedList<>();
        HashSet<Node> visited = new HashSet<>();
        Node start = graph.nodes.get(0);

        Node cur = start;
        visited.add(cur);
        PriorityQueue<Edge> heap= new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge e1, Edge e2){
                return e1.weight-e2.weight;
            }
        });
        for(Edge e: graph.nodes.get(cur.value).inEdges){
            heap.add(e);
        }
        for(Edge e: graph.nodes.get(cur.value).outEdges){
            heap.add(e);
        }

        while(visited.size()!=graph.nodes.size()){
            Edge e = heap.poll();
            while(visited.contains(e.from) && visited.contains(e.to)){//两个点都在集合里就不取
                e = heap.poll();
            }
            edges.add(e);
            cur = visited.contains(e.from)?e.to:e.from;//找一个不在集合里的点，起点或终点
            visited.add(cur);
            for(Edge edge: graph.nodes.get(cur.value).inEdges){
                heap.add(edge);
            }
            for(Edge edge: graph.nodes.get(cur.value).outEdges){
                heap.add(edge);
            }
        }


        return edges;
    }

    public static HashMap<Node,Integer> dijkstra(Graph graph, Node start){
        HashMap<Node,Integer> done = new HashMap<>();
        HashMap<Node,Integer> dis = new HashMap<>();
        //有需求这里可以放一个前缀表
        done.put(start,0);

        for(int i = 0; i<graph.nodes.size(); i++){
            Node node = graph.nodes.get(i);
            if(node!=start){
                dis.put(node,Integer.MAX_VALUE);
            }
        }
        Node cur = start;

        while(graph.nodes.size()!=done.size()){//最终的集合元素应该与点元素相同
            HashSet<Node> nodes = new HashSet<>(dis.keySet());

            //处理可能需要更新距离的点
            for(Edge edge: cur.outEdges){
                Node n = edge.to;
                if(dis.keySet().contains(edge.to)){
                     if(dis.get(n)>done.get(cur)+ edge.weight){
                         dis.put(n,done.get(cur)+ edge.weight);
                     }
                }
            }

            int min = Integer.MAX_VALUE;
            Node minNode=null;
            LinkedList<Node> temp = new LinkedList<>(dis.keySet());

            //找最短距离的点
            for(Node n: temp){
                int dis_ = dis.get(n);
                if(dis_<min) {
                    min = dis_;
                    minNode = n;
                }
            }

            //找出本轮加入结果集合的点，准备下一轮循环
            done.put(minNode,dis.get(minNode));
            dis.remove(minNode);
            cur = minNode;
        }

        return done;
    }



    public static void main(String[] args) {
        int[][] am =  {{0,1,1,0,3},
                       {0,0,0,2,0},
                       {0,0,0,1,5},
                       {0,0,0,0,3},
                       {0,0,0,0,3}};
//                        {{0,1,1,0},
//                        {0,0,0,2},
//                        {0,0,0,1},
//                        {0,0,0,0}};
        Graph g = new Graph(am);
        Map<Node,Integer> map = dijkstra(g,g.nodes.get(0));
        System.out.println(map);
    }
}
